#include <stdio.h>
#define MAX_HOUSES 40000

struct connection
{
    int distance[MAX_HOUSES];
    int neighbors;
};

struct connection houses[MAX_HOUSES];

int measure(int h1, int h2);

int main()
{
    int cases_num, houses_num, queries_num, house1, house2, distance;
    int i, j;
    for (i = 0; i < MAX_HOUSES;i++)
    {
        for (j = 0; j < MAX_HOUSES;j++)
        {
            houses[i].distance[j] = -1;
        }
        houses[i].neighbors = 0;
    }
    scanf("%d", &cases_num);
    for (i = 0; i < cases_num; i++)
    {
        scanf("%d %d", &houses_num, &queries_num);
        for (j = 0; j < houses_num-1; j++)
        {
            scanf("%d %d %d", &house1, &house2, &distance);
            houses[house1].distance[house2] = distance;
            houses[house2].distance[house1] = distance;
        }
        for (j = 0; j < queries_num; j++)
        {
            scanf("%d %d", &house1, &house2);
            distance = measure(house1, house2);
            printf("%d\n", distance);
        }
        printf("\n");
    }
    return 0;
}

int measure(int h1, int h2)
{
    int i;
    int min = 30000;
    int cmp;
    if(houses[h1].distance[h2]==-1)
    {
        for (i = 0; i < MAX_HOUSES;i++)
        {
            if(houses[h1].distance[i]!=-1)
            {
                cmp = houses[h1].distance[i] + measure(i, h2);
                if(cmp < min)
                {
                    min = cmp;
                }
            }
        }
        return min;
    }
    else
    {
        return houses[h1].distance[h2];
    }
}